#include <iostream>
#include <cstdio>
#include <set>
#include "regex.h"

namespace MyRegex {

using std::sprintf;
using std::set;

DirectedGraph::DirectedGraph(int vs) :
	vertices(vs),
	edges(0),
	adj(vs)
{
}

DirectedGraph::~DirectedGraph()
{
}

int
DirectedGraph::V() const
{
	return vertices;
}

int
DirectedGraph::E() const
{
	return edges;
}

vector<int>
DirectedGraph::adjacencies(int vertice) const
{
	return adj[vertice];
}

string
DirectedGraph::toString() const
{
	string res;
	char buf[128];

	sprintf(buf, "%d vertices, %d edges\n", vertices, edges);
	res += buf;
	for(int i = 0; i < vertices; i++) {
		sprintf(buf, "%d : ", i);
		res += buf;
		for(auto &item : adjacencies(i)) {
			sprintf(buf, "%d ", item);
			res += buf;	
		}
		res += "\n";
	}

	return res;
}

void
DirectedGraph::addEdge(int v, int w)
{
	edges++;
	adj[v].push_back(w);
}

DirectedGraphDFS::DirectedGraphDFS(const DirectedGraph &graph, int vertice) : 
	marked(graph.V(), false)
{
	dfs(graph, vertice);
}

DirectedGraphDFS::DirectedGraphDFS(const DirectedGraph &graph, const set<int> &vertices) :
	marked(graph.V(), false)
{
	for(auto &item : vertices) {
		if (!marked[item]) {
			dfs(graph, item);
		}
	}
}

bool
DirectedGraphDFS::isMarked(int vertice) const
{
	return marked[vertice];
}

void
DirectedGraphDFS::dfs(const DirectedGraph &graph, int vertice)
{
	marked[vertice] = true;
	for(auto &item : graph.adjacencies(vertice)) {
		if (marked[item]) {
			continue;
		}
		dfs(graph, item);
	}
}

NFA::NFA(const string &re) : 
	regex(re),
	regexMaxLength(re.length()),
	graph(regexMaxLength + 1)
{
	// build the nfa by a string
	stack<string::size_type> op;

	for(string::size_type i = 0; i < regexMaxLength; i++) {
		int lp = i;
		if (regex[i] == '(' || regex[i] == '|') {
			op.push(i);
		} else if (re[i] == ')') {
			int orPosition = op.top();
			op.pop();
			if (regex[orPosition] == '|') {
				lp = op.top();
				op.pop();
				graph.addEdge(lp, orPosition + 1);
				graph.addEdge(orPosition, i);
			} else {
				lp = orPosition;
			}
		}

		if (i < regexMaxLength - 1 && regex[i + 1] == '*') {
			graph.addEdge(lp, i + 1);
			graph.addEdge(i + 1, lp);
		}

		if (regex[i] == '(' || regex[i] == ')' || regex[i] == '*') {
			graph.addEdge(i, i + 1);
		}
	}

	std::cout << graph.toString() << std::endl;
}

bool
NFA::recognize(const string &s)
{
	set<int> status;
	set<int> match;
	DirectedGraphDFS dfs(graph, 0);
	for(int i = 0; i < graph.V(); i++)
		if (dfs.isMarked(i))
			status.insert(i);

	for(string::size_type i = 0; i < s.length(); i++) {
		match.clear();
		for(auto &item: status)
			if (item < (int)regexMaxLength)
				if (regex[item] == s[i] || regex[item] == '.')
					match.insert(item + 1);

		status.clear();
		dfs = DirectedGraphDFS(graph, match);
		for (int i = 0; i < graph.V(); i++)
			if (dfs.isMarked(i))
				status.insert(i);
	}

	for(auto &item : status)
		if (item == (int) regexMaxLength)
			return true;

	return false;
}

Regex::Regex(const string &re) :
	regex(re)
{
}

bool
Regex::recognize(const string &s)
{
	NFA nfa(regex);

	return nfa.recognize(s);
}
};
